[Coding006] DataStructure
顺序表中元素的插入

Ben 2023/07/27

More coding records
Get the knowledge flowing and circulating! :)

标题：顺序表的基本操作与元素的插入（C语言版）Demo代码→ 插入函数的手绘图解释执行结果重点代码解释

标题：顺序表的基本操作与元素的插入（C语言版）

本部分操作：关于顺序表的清除、求长度、判空、新元素插入、遍历。

Demo代码


xxxxxxxxxx
141
1
// 顺序表的初始化
2

3
#include"stdio.h"  
4
#include"malloc.h"  // malloc
5

6
#include"stdlib.h"  // exit
7

8
#define List_InitSize 100
9
#define List_Increment 10
10

11
typedef struct{
12
    int *elem;  // 存储空间基址
13
    
14
    int length;  // 当前长度
15
    int listsize; // 当前分配的存储容量(以sizeof(int)为单位)
16
}SqList;
17

18
// 【C段代码】调用示例：
19
// SqList l; 
20
// Init_SqList03(&l);
21
// 含义解读：创建一个变量，这个变量的地址传入函数。这个函数没有返回值，通过函数操作完之后，传入的参数在后面可以直接被调用，这个函数执行完之后，传入的参数也已经被修改了，why? 因为这个函数的参数就是地址。函数内部的操作都是按照地址找到目标变量的老家，然后一顿操作之后。老家就变样了（即，此时的l就是已经初始化之后的样子了！）
22
void Init_SqList03(SqList *L)
23
{
24
    L->elem = (int*)malloc(List_InitSize * sizeof(int));
25
    if (!L->elem)
26
    {
27
        exit(-2);
28
    }
29

30
    L->length = 0;
31
    L->listsize = List_InitSize;
32
}
33

34
void DestroyList_Sq(SqList *L)
35
{
36
    free(L->elem);      // free((*L).elem);
37
    L->elem = NULL;     // (*L).elem = NULL;  // 置空防止野指针 
38
    L->length = 0;      // (*L).length = 0; 
39
    L->listsize = 0;    // (*L).listsize = 0; 
40
} 
41

42
// 清除 
43
int ClearList_Sq(SqList *L)
44
{
45
    // 直接把L->length置为0即可，这样在下一次插入操作的时候，之前的元素就被覆盖了。（其实，在计算机内部，当你申请了一段内存用于存放元素的时候，这个内存中已经存放了一些随机数。这些随机数会在插入操作时被覆盖。）
46
    L->length = 0;
47
    return 0;
48
}
49

50
/*
51
// 清除顺序表：无返回值版 
52
void ClearList(SqList *L)
53
{
54
    L->length = 0;
55
}
56
*/
57

58
// 求长度 
59
int ListLength_Sq(SqList *L)
60
{
61
    // 直接返回顺序表中元素的长度即可。注意，顺序表的长度和顺序表的容量是两个概念。顺序表的容量是表示这个表能存放多少元素。顺序表的长度表示这个顺序表中已经存在了多少元素。
62
    return L->length;
63
}
64

65
// 判空 
66
int ListIsEmpty_Sq(SqList *L)
67
{
68
    if(L->length == 0)
69
        return 1;
70
    else
71
        return 0;
72
}
73

74
// 画个图，形象地说一下这个问题。 
75
int ListInsert_Sq(SqList *L, int i, int e)
76
{
77
    // 这里的i，要想清楚它的含义。这里的i是指，在第i位之前（i从1开始）。比如，在第0号位插入，就是在第1号位之前插入，即，i=1。 
78
    // * 假设顺序表初始长度为10，目前里面已经有了1个元素。我们可以插入的位置，用计算机语言描述插入位置的下标可以是（0号位，1号位。不能插入2号位，因为是顺序存储，不能跳）
79
    // * 那么，用大众的思维，我们如果要插入0号位。那就是说，在第1个位置之前插入，即i=1。对应的，该位置的地址可以利用语句 [(*L).elem + i - 1]表示。
80
    // * 并且，如果我们要插入在第1号位，在本例中，1号位就是顺序表的最后1个位置的后面。那就是说，在第2个位置插入。那么，2怎么来的呢？
81
    // ** 2应该是当前顺序表内元素的个数+1.换句话说，在最后一位插入，就是在当前顺序表的length + 1位插入。 
82
    // ** 比如，现在顺序表中有3个元素。我想在最后1位之后插入。那就是获取L的length(也就是3),在这个位置后面插入就行了，即i要再增加1位，变为4，因为对应的代码应该延续上面的，有一个减1的操作。 [(*L).elem + 4 - 1]
83
    // * 所以，这里我们要判断的是，待插入位置，不能小于1（大众思维）；不能大于length+1（比如已存3个元素，我们最多在第4个位置插入） 
84
    
85
    if((i < 1) || i > L->length + 1)
86
        return 0;
87
    
88
    if (L->length >= L->listsize)
89
    {
90
        int *newbase = (int*)realloc(L->elem, (L->listsize + List_Increment) * sizeof(int));
91
        if (!newbase)
92
        {
93
            exit(-2);
94
        }
95
        
96
        L->elem = newbase;
97
        L->listsize = L->listsize + List_Increment;
98
    }
99
    
100
    int *q = L->elem + i - 1;  // q指向待插入的位置
101
    int *p; 
102
    for (p = L->elem + L->length - 1; p >= q; p--)
103
    {
104
        *(p + 1) = *(p);
105
    }
106
    // 腾出位置后，在q位置插入元素e
107
    *q = e;
108
    // 插入元素后，长度别忘记加啦~ 
109
    L->length++;
110
    
111
    return 0; 
112
}
113

114
void ListTraverse_Sq(SqList *L)
115
{
116
    int i;
117
    for (i = 0; i < L->length; i++)
118
    {
119
        printf("%d ", *(L->elem + i));  // L->elem指向的是元素数组的首地址
120
    }
121
    printf("\n");
122
}
123

124
int main()
125
{
126
    SqList Lc;  // 操作符为 "." 
127
    Init_SqList03(&Lc);
128
    
129
    // 初始情况下，现有的元素的个数，即目前顺序表的长度（length），总容量（listsize）
130
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
131
    
132
    ListInsert_Sq(&Lc, 1, 3);  // 在1号位置插入元素3
133
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
134
    ListTraverse_Sq(&Lc);  // 打印出来看看目前的情况
135
    
136
    ListInsert_Sq(&Lc, 1, 4);  // 在1号位置插入4，那刚刚那个元素3要后移！
137
    printf("Lc.length=%d, Lc.listsize=%d\n", Lc.length, Lc.listsize);
138
    ListTraverse_Sq(&Lc);  // 打印出来看看！
139
    
140
    return 0; 
141
}

→ 插入函数的手绘图解释

seq_ins

执行结果


xxxxxxxxxx
9
1
Lc.length=0, Lc.listsize=100
2
Lc.length=1, Lc.listsize=100
3
3
4
Lc.length=2, Lc.listsize=100
5
4 3
6

7
--------------------------------
8
Process exited after 0.02532 seconds with return value 0
9
请按任意键继续. . .

重点代码解释

聊聊整个代码中最重要的代码段 —— 元素的插入。
余量的判断，目标：如果目前的容量已经满了，咱们需要再申请一部分空间来存放新元素；
元素的移动，目标：把待插入的位置腾出来。
元素的插入，目标：把新元素赋予新的位置。

[Coding006] DataStructure 顺序表中元素的插入

标题：顺序表的基本操作与元素的插入（C语言版）

Demo代码

→ 插入函数的手绘图解释

执行结果

重点代码解释

[Coding006] DataStructure
顺序表中元素的插入